/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
/*
层次遍历的思想
在遍历每一层时判断当前层数是奇数还是偶数，如果是奇数就正着存储，偶数就倒着存储
*/
class Solution {
public:
    vector<vector<int> > Print(TreeNode* root) {
        vector<int>vec;
        vector<vector<int>>ans;
        if(root==nullptr)
            return ans;
        queue<TreeNode*> q;
        q.push(root);
        int level=1;
        while(!q.empty())
        {
            int len=q.size();
            for(int i=0;i<len;i++)
            {
                auto cur=q.front();
                q.pop();
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
                if(level%2)
                {
                    vec.push_back(cur->val);
                }else
                {
                    vec.insert(vec.begin(), cur->val);
                }
            }
            ans.push_back(vec);
            vec.clear();
            level++;
           }
        return ans;
    }
    
};